1. Field of the Invention
The present invention relates to an information processing apparatus, an information processing method, a recording medium and a computer program and, in particular, to an information processing apparatus, an information processing method, a recording medium and a computer program, for use in determining as a solution a set of genes appropriate for solving a target problem.
2. Description of the Related Art
Genetic search algorithm is used as one of algorithms for determining an approximate solution to a given problem.
In accordance with the genetic search algorithm in the related art, data (solution candidate) is represented as a gene, a plurality of genes are prepared, and an evaluation value of each gene is then calculated. A gene having a higher evaluation value is selected in a next generation with a higher priority, and used as a seed for crossover or mutation operations. With generations in progress, a solution is searched.
The genetic search method in the related art is described below with reference to FIG. 1.
Two sets, each containing genes, namely, solution candidates of a predetermined number m, are prepared. The two sets are referred to as a “current generation” and a “next generation.” In a first generation as the current generation, m genes are randomly generated. Through an evaluation function, the evaluation value of each gene in the current generation is calculated.
After the m genes in the current generation are given respectively evaluation values, crossover, mutation and copy operations are performed based on the evaluation values. New genes are also generated randomly. The results are then stored as m genes in the next generation. The crossover, mutation, and copy operations and the random generation of a new gene are performed at predetermined rate.
The crossover operation is modeled from living creatures that produce offspring by mating. In the crossover operation, two genes in the current generation are selected, and a gene in a next generation is generated with part of the gene in the current generation exchanged. A plurality of methods are available in the crossover operation by selecting crossover points, namely, one crossover point, two crossover points, or multiple crossover points. The mutation operation is modeled from mutation of genes observed in living creatures. One gene is selected from the current generation and part of the selected gene is changed. In the copy operation, one gene is selected from the current generation, and the selected gene is directly stored as a gene for the next generation.
When any of the crossover, mutation and copy operations is performed, a gene selection process of the current generation is performed. The gene selection is performed using an algorithm that allows a gene having a higher evaluation value to be selected with a higher priority, based on the evaluation values of the genes of the current generation. A plurality of algorithms for the gene selection have been proposed, including ranking selection, tournament selection, elite selection, etc.
An example of FIG. 1 is described. A gene number 2 having an evaluation value 0.8 and a gene number 5 having an evaluation value 0.6 are selected and copied to a next generation as having a higher evaluation value with higher priority. The gene number 2 having an evaluation value 0.8 is selected and mutated as having a high evaluation value with higher priority, and a gene generated through mutation is stored for the next generation. From among the genes in the current generation, the gene number 2 having an evaluation value 0.8 and the gene number 5 having an evaluation value 0.6 are selected and crossed over, and a gene generated through the crossover operation is stored for the next generation. Genes are randomly generated at a predetermined rate, and stored for the next generation.
With the genes for the next generation prepared, the gene group of those genes is treated as genes in the current generation and the evaluation values of the genes in the current generation are calculated. The crossover, the mutation and the copy operations are performed based on the evaluation values, and new genes are then generated randomly. Results are then stored as m genes for a next generation. If a gene reaches the highest evaluation value that can be exceeded no longer, or if a predetermined number of generations has passed, a gene having the highest evaluation value in the current generation is output as a “solution.”
For example, the generation search method is applied to generate an algorithm that allows a feature quantity to be selected at a high accuracy level at a high speed from content data such as music data as disclosed in International Publication No. WO2007/049641.
The genetic search method used in International Publication No. WO2007/049641 is described with reference to FIGS. 2A. and 2B.
The genetic search method of the related art described with reference to FIG. 1 outputs one gene as a solution appropriate for solving a target problem. In contrast, the genetic search method disclosed in International Publication No. WO2007/049641 outputs a set of genes appropriate for solving a target problem.
The genetic search method disclosed in International Publication No. WO2007/049641 is intended to determine “a gene group composed a plurality of genes” that allow an approximate solution to the target problem to be accurately determined instead of a “single gene” that allows an approximate solution to the target problem to be accurately determined. In order to generate the gene group solving the target problem, a plurality of gene lists, each listing a plurality of genes, are used. Let m represent the number of gene lists and n represent the number of genes listed in a single gene list.
The evaluation values are calculated on a per gene list basis instead of on a per gene basis. A gene list is selected from the gene lists of the current generation based on the evaluation values provided on a per gene list basis. The copy, crossover and mutation operations and the random generation of the new gene list are performed to generate m gene lists of a new generation.